Packet classification, which is widely used on the Internet, is the core mechanism that enables routers to perform many networking services such as firewall packet filtering, virtual private networks (VPNs), network address translation (NAT), quality of service (QoS), load balancing, traffic accounting and monitoring, differentiated services (Diffserv), etc. As more services are deployed on the Internet, packet classification grows in demand and importance.
The function of a packet classification system is to map each packet to a decision (i.e., action) according to a sequence (i.e., order list) of rules, which is called a packet classifier. Each rule in a packet classifier has a predicate over some packet header fields and a decision to be performed upon the packets that match the predicate. To resolve possible conflicts among rules in a classifier, the decision for each packet is the decision of the first (i.e., highest priority) rule that the packet matches. Table 1 below shows an example packet classifier of two rules. The format of these rules is based upon the format used in Access Control Lists on Cisco routers.
TABLE 1RuleSource IPDestination IPSource PortDestination PortProtocolActionr11.2.3.0/24192.168.0.1[1.65534][1.65534]TCPacceptr2*****discard
To process the never-ending supply of packets at wire speed, using Ternary Content Addressable Memories (TCAMs) to perform packet classification has become the de facto standard for high-speed routers on the Internet. A TCAM is a memory chip where each entry can store a packet classification rule that is encoded in ternary format. Given a packet, the TCAM hardware can compare the packet with all stored rules in parallel and then return the decision of the first rule that the packet matches. Thus, it takes O (1) time to find the decision for any given packet. In 2003, most packet classification devices shipped were TCAM-based. More than 6 million TCAM devices were deployed worldwide in 2004.
Despite their high speed, TCAMs have their own limitations with respect to packet classification. TCAMs can only store rules that are encoded in ternary format. In a typical packet classification rule, source IP address, destination IP address, and protocol type are specified in prefix format, which need to be converted to one or more prefixes before being stored in TCAMs. This can lead to a significant increase in the number of TCAM entries needed to encode a rule. For example, 30 prefixes are needed to represent the single range [1,65534], so 30×30=900 TCAM entries are required to represent the single rule (r1) in Table 1.
TCAMs have limited capacity. The largest TCAM chip available on the market has 18 Mb while 2 Mb and 1 Mb chips are most popular. Given that each TCAM entry has 144 bits and a packet classification rule may have a worst expansion factor of 900, it is possible that an 18 Mb TCAM chip cannot store all the required entries for a modest packet classifier of only 139 rules. While the worst case may not happen in reality, this is certainly an alarming issue. Furthermore, TCAM capacity is not expected to increase dramatically in the near future due to other limitations that we will discuss next.
TCAM chips also consume large amounts of power and generate large amounts of heat. For example, a 1 Mb TCAM chip consumes 15-30 watts of power. Power consumption together with the consequent heat generation is a serious problem for core routers and other networking devices.
TCAMs occupy much more board space than SRAMs. For networking devices such as routers, area efficiency of the circuit board is a critical issue.
TCAMs are expensive. For example, a 1 Mb TCAM chip costs about 200˜250 U.S. dollars. TCAM cost is a significant fraction of router cost.
This section provides background information related to the present disclosure which is not necessarily prior art.